#include "fatal.h"
#include "hashsep.h"
#include <stdlib.h>

#define MinTableSize (10)

struct ListNode
{
    ElementType Element;
    Position Next;
};

typedef Position List;

/* List *TheList will be an array of lists, allocated later */
/* The lists use headers (for simplicity), */
/* though this wastes space */
struct HashTbl
{
    int TableSize;
    List *TheLists;
};

/* Return next prime; assume N >= 10 */
static int
NextPrime(int N)
{
    int i;

    if (N % 2 == 0)
        N++;
    for (;; N += 2)
    {
        for (i = 3; i * i <= N; i += 2)
            if (N % i == 0)
                goto ContOuter; /* Sorry about this! */
        return N;
    ContOuter:;
    }
}

/* Hash function for ints */
Index Hash(ElementType Key, int TableSize)
{
    return Key % TableSize;
}

/* START: fig5_8.txt */
HashTable
InitializeTable(int TableSize)
{
    HashTable H;
    int i;

    /* 1*/ if (TableSize < MinTableSize)
    {
        /* 2*/ Error("Table size too small");
        /* 3*/ return NULL;
    }

    /* Allocate table */
    /* 4*/ H = malloc(sizeof(struct HashTbl));
    /* 5*/ if (H == NULL)
        /* 6*/ FatalError("Out of space!!!");

    /* 7*/ H->TableSize = NextPrime(TableSize);

    /* Allocate array of lists */
    /* 8*/ H->TheLists = malloc(sizeof(List) * H->TableSize);
    /* 9*/ if (H->TheLists == NULL)
        /*10*/ FatalError("Out of space!!!");

    /* Allocate list headers */
    /*11*/ for (i = 0; i < H->TableSize; i++)
    {
        /*12*/ H->TheLists[i] = malloc(sizeof(struct ListNode));
        /*13*/ if (H->TheLists[i] == NULL)
            /*14*/ FatalError("Out of space!!!");
        else
            /*15*/ H->TheLists[i]->Next = NULL;
    }

    /*16*/ return H;
}
/* END */

/* START: fig5_9.txt */
Position
Find(ElementType Key, HashTable H)
{
    Position P;
    List L;

    /* 1*/ L = H->TheLists[Hash(Key, H->TableSize)];
    /* 2*/ P = L->Next;
    /* 3*/ while (P != NULL && P->Element != Key)
        /* Probably need strcmp!! */
        /* 4*/ P = P->Next;
    /* 5*/ return P;
}
/* END */

/* START: fig5_10.txt */
void Insert(ElementType Key, HashTable H)
{
    Position Pos, NewCell;
    List L;

    /* 1*/ Pos = Find(Key, H);
    /* 2*/ if (Pos == NULL) /* Key is not found */
    {
        /* 3*/ NewCell = malloc(sizeof(struct ListNode));
        /* 4*/ if (NewCell == NULL)
            /* 5*/ FatalError("Out of space!!!");
        else
        {
            /* 6*/ L = H->TheLists[Hash(Key, H->TableSize)];
            /* 7*/ NewCell->Next = L->Next;
            /* 8*/ NewCell->Element = Key; /* Probably need strcpy! */
            /* 9*/ L->Next = NewCell;
        }
    }
}
/* END */

ElementType
Retrieve(Position P)
{
    return P->Element;
}

void DestroyTable(HashTable H)
{
    int i;

    for (i = 0; i < H->TableSize; i++)
    {
        Position P = H->TheLists[i];
        Position Tmp;

        while (P != NULL)
        {
            Tmp = P->Next;
            free(P);
            P = Tmp;
        }
    }

    free(H->TheLists);
    free(H);
}
